9021. Количество чисел вида 2^x * 3^y

Найдите количество целых чисел на отрезке [a, b], представимых в виде 2^x * 3^y при x ≥ 0, y ≥ 0.

Вход. Содержит не более 10⁶ строк. Каждая строка содержит два целых числа a и b (0 ≤ a ≤ b ≤ 10¹⁸), задающих один запрос.

Выход. Для каждого запроса выведите в отдельной строке количество целых чисел на отрезке [a, b] включительно, которые можно представить в виде 2^x * 3^y.

Пример входа	Пример выхода
1 10 100 200	7 5

РЕШЕНИЕ

бинарный поиск

Анализ алгоритма

Чисел вида 2^x * 3^y, не превышающих 10¹⁸, не так уж много. Сгенерируем их и сохраним в массиве v.

Количество искомых чисел f(a, b) на отрезке [a, b] можно найти по формуле:

f(0, b) – f(0, a – 1)

Здесь f(0, q) обозначает количество чисел вида 2^x * 3^y, не превышающих q. Ответ на этот запрос можно найти с помощью бинарного поиска на массиве v.

Пример

Сгенерируем все числа вида 2^x * 3^y, не превышающие 200.

Отрезку [1; 10] принадлежит 7 чисел (выделены синим).

Отрезку [100; 200] принадлежит 5 чисел (выделены зеленым).

Найдем решение для отрезка [10; 20]:

upper_bound(v.begin(), v.end(), 20) – upper_bound(v.begin(), v.end(), 9) = 3

Действительно, отрезку [10; 20] принадлежит 3 числа искомого вида:

12, 16, 18

Реализация алгоритма

Объявим константу MAX = 10¹⁸ и рабочий массив v.

#define MAX 1000000000000000000LL

vector<long long> v;

Функция preprocess генерирует все числа вида 2^x * 3^y, не превышающие 10¹⁸, и сохраняет их в массиве v. Для каждого значения x = 1, 2, 4, 8, … перебираем числа y = 1, 3, 9, 27, … до тех пор, пока x * y < MAX.

void preprocess()

{

long long x = 1, y = 1;

while (x < MAX)

{

while (x * y < MAX)

{

v.push_back(x * y);

y *= 3;

}

x *= 2;

y = 1;

}

Отсортируем числа в массиве v.

sort(v.begin(), v.end());

}

Основная часть программы. Генерируем массив чисел вида 2^x * 3^y.

preprocess();

Читаем запрос – отрезок [a, b]. Количество искомых чисел на этом отрезке вычисляется по формуле:

f(a, b) = f(0, b) – f(0, a – 1)

while (scanf("%lld %lld", &a, &b) == 2)

{

res = upper_bound(v.begin(), v.end(), b) –

upper_bound(v.begin(), v.end(), a - 1);

printf("%lld\n", res);

}